package example;

/**
 * A utility class that is used to create and populate tri-nary trees.
 *
 * @author Dallas Rosson (dallasjrosson@gmail.com)
 * @version 1.0
 */
public class TrinaryTreeCreator {
	
	/**
	 * The root Node.
	 */
	private Node myRoot;
	
	/**
	 * Creates a new TrinaryTreeCreator.
	 */
	public TrinaryTreeCreator() {
		
		// Default constructor.		
	}
	
	// Utility methods.
	
	/**
	 * Populates the tree with the values of the passed in array of Integers.
	 * 
	 * @param the_values The array of Integers to populate the tree.
	 */
	public void Populate(final int[] the_values) {
		
		// Create the root.
		myRoot = new Node(the_values[0]);
		
		// Insert values into the tree.
		for (int i = 1; i < the_values.length; i++) {
			
			Insert(myRoot, the_values[i]);
		}
		
	}
	
	/**
	 * Inserts the passed in value into the appropriate position in the tree.  If the
	 * position is already filled by another value, recursively calls this method with
	 * that value's node as the parent.
	 * 
	 * @param the_parent The parent Node.
	 * @param the_val The value to be added to the tree.
	 */
	public void Insert(final Node the_parent, final int the_val) {
		
		/*
		 * If the value to be inserted is less than the current node value,
		 * place that value in the left child of this Node.
		 */
		if (the_val < the_parent.value) {
			
			// Left child exists.
			if (the_parent.left != null) {
				
				Insert(the_parent.left, the_val);
				
			} else { // Left child does not exist.  Create it and set value to the_val.
				
				the_parent.left = new Node(the_val);
			}
		} else if (the_val > the_parent.value) {
			
			/*
			 * If the value to be inserted is greater than the current node value,
			 * place that value in the right child of this Node.
			 */
			
			// Right child exists.
			if (the_parent.right != null) {
				
				Insert(the_parent.right, the_val);
				
			} else { // Right child does not exist.  Create it and set value to the_val.
				
				the_parent.right = new Node(the_val);
			}
		} else { 
			
			/* 
			 * If the value to be inserted is equal to the current node value,
			 * place that value in the middle child of this Node.
			 */
			
			// Middle child exists.
			if (the_parent.middle != null) {

				Insert(the_parent.middle, the_val);

			} else { // Middle child does not exist.  Create it and set value to the_val.

				the_parent.middle = new Node(the_val);
			}
        }		
	}
	
	/**
	 * Prints the tree values recursively in a Depth First Search method. Prints null for Nodes
	 * that don't exist.
	 */
	public void print() {
		
		if (myRoot != null) {

			System.out.println(myRoot.value);
			print(myRoot.left);
			print(myRoot.middle);
			print(myRoot.right);
		}
	}
	
	/**
	 * Prints the tree values recursively in a Depth First Search method. Prints null for Nodes
	 * that don't exist.
	 * 
	 * @param the_root The root Node of the tree.
	 */
	private void print(final Node the_root) {
		
		if (the_root != null) {
			
			System.out.println(the_root.value);
			print(the_root.left);
			print(the_root.middle);
			print(the_root.right);
			
		} else {
			
			System.out.println("null");
		}
	}
	
	// Inner class.
	
	/**
	 * A tree node.
	 * 
	 * @author Dallas Rosson (dallasjrosson@gmail.com)
	 * @version 1.0
	 */
	static class Node {
		
		/**
		 *  Node value is less than this Node.
		 */
		Node left;
		
		/**
		 * Node value is equal to this Nodes.
		 */
		Node middle;
		
		/**
		 * Node value is greater than this Nodes.
		 */
		Node right;
		
		/**
		 * The Nodes value.
		 */
		int value;
		
		/**
		 * Creates a new Node.
		 * 
		 * @param the_value The value of the Node.
		 */
		public Node(final int the_value) {
			
			value = the_value;
		}
	}
}




